1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
const int maxn = 1005;
const int maxV = 5005;
const int INF = 0x3f3f3f3f;
using namespace std;
struct E{
int to, nxt;
}e[maxn];
int head[maxn], tot = 0;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
int n, res[maxn], x[maxn];
int f[maxV];
void dfs(int cur){
for (int i = head[cur]; i; i = e[i].nxt) dfs(e[i].to);
for (int i = 0; i <= x[cur]; i++) f[i] = INF; f[0] = 0;
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
for (int j = x[cur]; j >= 0; j--){
int tmp = INF;
if (j >= res[v]) tmp = min(tmp, f[j - res[v]] + x[v]);
if (j >= x[v]) tmp = min(tmp, f[j - x[v]] + res[v]);
f[j] = tmp;
}
}
for (int i = 0; i <= x[cur]; i++) res[cur] = min(res[cur], f[i]);
}
int main(){
scanf("%d", &n); memset(res, 0x3f, sizeof res);
for (int f, i = 2; i <= n; i++){
scanf("%d", &f); addedge(f, i);
}
for (int i = 1; i <= n; i++) scanf("%d", x + i);
dfs(1);
if (res[1] != INF) puts("POSSIBLE");
else puts("IMPOSSIBLE");
return 0;
}
|